package com.example.javaproject.datastructure.tree;

/**
 * 二叉搜索树
 * <p>
 * 在二叉搜索树中，一个节点的左子节点关键字值小于这个节点，右子节点的关键字值大于或者等于这个值
 * 其结构如下
 *
 * <p>
 * <img width="640" height="320" src="https://img-blog.csdnimg.cn/8d450c68b5944a30b708657deba51c7d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA54ix5pWy5Luj56CB55qE5LiJ5q-b,size_18,color_FFFFFF,t_70,g_se,x_16">
 * <p/>
 */
public class MSearchBinaryTree implements MTree {
    /**
     * 根节点
     */
    private Node root;

    @Override
    public Node find(int key) {
        Node current = root;
        while (current != null) {
            if (key < current.key) {          // 当前值比查找值大，搜索左子树
                current = current.leftNode;
            } else if (key > current.key) {   // 当前值比查找值小，搜索右子树
                current = current.rightNode;
            } else {
                return current;
            }
        }
        return null;
    }

    @Override
    public boolean insert(int key) {
        Node newNode = new Node(key);
        if (root == null) {
            root = newNode;
            return true;
        }

        Node current = root;
        while (true) {
            if (key < current.key) {  // 当前节点的值大于key，那么搜索左边节点
                if (current.leftNode == null) {
                    current.leftNode = newNode;
                    return true;
                }
                current = current.leftNode;
            } else {
                if (current.rightNode == null) {
                    current.rightNode = newNode;
                    return true;
                }
                current = current.rightNode;
            }
        }
    }


    //中序遍历
    public void infixOrder(Node current) {
        if (current != null) {
            infixOrder(current.leftNode);
            System.out.print(current.data + " ");
            infixOrder(current.rightNode);
        }
    }

    //前序遍历
    public void preOrder(Node current) {
        if (current != null) {
            System.out.print(current.data + " ");
            infixOrder(current.leftNode);
            infixOrder(current.rightNode);
        }
    }

    //后序遍历
    public void postOrder(Node current) {
        if (current != null) {
            infixOrder(current.leftNode);
            infixOrder(current.rightNode);
            System.out.print(current.data + " ");
        }
    }

    //找到最大值
    public Node findMax() {
        Node current = root;
        Node maxNode = current;
        while (current != null) {
            maxNode = current;
            current = current.rightNode;
        }
        return maxNode;
    }

    //找到最小值
    public Node findMin() {
        Node current = root;
        Node minNode = current;
        while (current != null) {
            minNode = current;
            current = current.leftNode;
        }
        return minNode;
    }

    @Override
    public boolean delete(int key) {
        Node current = root;
        Node parent = root;
        boolean isleftNode = false;
        //查找删除值，找不到直接返回false
        while (current.key != key) {
            parent = current;
            if (current.key > key) {
                isleftNode = true;
                current = current.leftNode;
            } else {
                isleftNode = false;
                current = current.rightNode;
            }
            if (current == null) {
                return false;
            }
        }
        //如果当前节点没有子节点
        if (current.leftNode == null && current.rightNode == null) {
            if (current == root) {
                root = null;
            } else if (isleftNode) {
                parent.leftNode = null;
            } else {
                parent.rightNode = null;
            }
            return true;

            //当前节点有一个子节点，右子节点
        } else if (current.leftNode == null && current.rightNode != null) {
            if (current == root) {
                root = current.rightNode;
            } else if (isleftNode) {
                parent.leftNode = current.rightNode;
            } else {
                parent.rightNode = current.rightNode;
            }
            return true;
            //当前节点有一个子节点，左子节点
        } else if (current.leftNode != null && current.rightNode == null) {
            if (current == root) {
                root = current.leftNode;
            } else if (isleftNode) {
                parent.leftNode = current.leftNode;
            } else {
                parent.rightNode = current.leftNode;
            }
            return true;
        } else {
            //当前节点存在两个子节点
            Node successor = getSuccessor(current);
            if (current == root) {
                successor = root;
            } else if (isleftNode) {
                parent.leftNode = successor;
            } else {
                parent.rightNode = successor;
            }
            successor.leftNode = current.leftNode;
        }
        return false;

    }

    public Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightNode;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftNode;
        }
        //后继节点不是删除节点的右子节点，将后继节点替换删除节点
        if (successor != delNode.rightNode) {
            successorParent.leftNode = successor.rightNode;
            successor.rightNode = delNode.rightNode;
        }

        return successor;
    }

    public static void main(String[] args) {
        MSearchBinaryTree bt = new MSearchBinaryTree();
        bt.insert(50);
        bt.insert(20);
        bt.insert(80);
        bt.insert(10);
        bt.insert(30);
        bt.insert(60);
        bt.insert(90);
        bt.insert(25);
        bt.insert(85);
        bt.insert(100);
        bt.delete(10);//删除没有子节点的节点
        bt.delete(30);//删除有一个子节点的节点
        bt.delete(80);//删除有两个子节点的节点
        System.out.println(bt.findMax().data);
        System.out.println(bt.findMin().data);
        System.out.println(bt.find(100));
        System.out.println(bt.find(200));

    }
}
